3D simulation has known a great success during the last three decades in various and large audiences of users: from engineers verifying how a system in design stage will behave in reality, to scientists exploring or demonstrating theoretical conceptions, to general public playing video games or enjoying 3D animation films. 3D simulation knows many evolutions over the past three decades and is still having a growing momentum. This is to answer audiences' needs for more complex and more realistic behaviors (Multi-Body Rigid Dynamics, Human Simulation, Cloth Simulation, Particle Simulation . . . ), for wider populations and typologies of objects and for wider scale.
3D simulation has to meet real-time requirements, which was more particularly initiated in the video game industry, by developing specific technologies to support a massive number of users interacting in large scale virtual worlds. A real-time response has to be offered at any time to the connected users, regardless of their number, and regardless of the induced computation costs for solving and rendering of the application.
Massively Multi-user On line applications (MMOs) allow a large number of users to simultaneously use an application such as real-world phenomena simulator, immersive applications, and so on. Similarly, Massively Multi-user On line Games (MMOG) allow a large number of garners to play simultaneous a video game. MMOs and MMOGs notably rely on computer networks, e.g. the Internet, for allowing the users or garners to connect to the applications or video games. Throughout this specification the word “application” and “video games” will be understood as to be synonymous, and the terms MMO and MMOG will be indifferently used.
MMOs involve complex and large virtual environments which are desired to be rendered in as much detail as possible, in as close to real time as possible, in order to provide users or game players with a more realistic experience. MMOs are specifically designed for the representation and the manipulation of 3D scenes, and are typically used on the end-user's computer for applications that require interactive, sequential, real-time 3D scene generation. As the user interacts with the 3D scene, the computer redraws the 3D representations rapidly enough to convey to the user the sense of a continuous, ongoing reality in which the user is participating. The scene is composed of many separate objects that can be manipulated by user when interacting with the 3D scene. Thus, MMOs involve large data volumes, high data rates and high data complexity is generally required in order to manage large numbers of users participating in real time in a spatially complex and highly detailed virtual environment.
MMOs are typically used for simulating real-world phenomena within computer models; for instance Multi-Body Rigid Dynamics, Human Simulation, Cloth Simulation, Particle Simulation. Simulations require accurate data and algorithms that describe real-world phenomena, such as the physical properties (strength, elasticity, etc.) of the materials used in a manufacturing process and the product to create a simulation of the process and a simulation of a product in use. 3D CAD/CAM (Computer Aided Design, Computer Aided Manufacturing) tools allow to create 3D representations of the product or component parts. MMO is also referred to as 3D experience, that is, a virtual environment in which engineers study the behaviours of objects; typically the simulated environment is an industry environment.
MMO's, just like MMOG's, must be scalable to dynamically adapt to the perpetually changing work-load, maintaining thus real-time performance. Scalability notably comprises the number of users that can simultaneously use the application, the number of computing resources for computing the simulations, the number of simultaneous interactions between objects of the 3D scene allowed by the application, and so on.
For MMOG's, the number of users may vary significantly, as well as the positional and graphical attributes of all contained dynamic objects. Nevertheless, the surrounding scenery is set once for all and the typology of dynamic objects and the supported behavior classes are predefined, before the game starts. Said otherwise, 3D scenes in MMOGs comprise a number of predetermined characteristics that strongly limit the needs of computing resources; thus improving scalability. Forecasting the needs of computing resources is thus possible.
On the contrary, for advanced MMOs, the scenery and population typology of the 3D scene can evolve and enrich, especially while application is running. Indeed, MMOs aim at simulating real-world phenomena, wherein the behavior of objects is dynamic and excludes predefined behavior classes. Consequently, 3D scenery in MMOs cannot use predefined characteristics as for MMOGs.
Thus, even if a 3D Experience has the same kind of real-time and massiveness constraints as MMOG, it has a specific and stringent requirement for far more sophisticated, realistic and accurate physical behaviors, therefore demanding computational power.
As one single solver cannot cope with all the solving computations in real-time, parallelization techniques are required. In few words, the 3D Experience is partitioned into so called parts or zones, each of them dealing with a specific spatial region of the 3D scene. As the computing cost of such parts varies over time—because their object populations evolve and because volumes of interactions within change as well-, it is necessary to dynamically dispatch all these parts among solvers to achieve optimal use of the CPU resources for granting real-time response. This need is commonly referred to as dynamic load balancing.
Considering technologies applicable to real-time, mostly those used in MMOG's, they are not suitable for the purpose of 3D Experience. MMOG's load balancing takes the liberty to alter the phenomenology of the scene: users can be transferred to another part, objects can be removed from high load part, interactions can be neutralized in high load parts, in a way it does not seem odd to the user. So, physics of the game is hacked to adjust to hardware limitations, therefore losing more realism. For the 3D Experience, physics is a definitively a constraint to satisfy, with a fixed degree of realism, and therefore cannot be taken as adjustment parameter.
Load balancing problem is also addressed in domains such as Finite Element Methods, which proposes a wide range of efficient solutions. But as real-time is out of the concern scope, all of these adjustment strategies are not grounded on tuning parameters explicitly related to computational time performance, but rather on ad-hoc tuning depending of the solving algorithms used, on the geometrical characteristics of the model (e.g. mesh) and on transient numerical properties (e.g. nonlinearities) with are specific to studied use-case.
Within this context, there is still a need for an improved method, computer program, and system achieving fair load balancing among an optimal number of solvers, running at their optimal capacity, avoiding overhead prone to corrupt real-time response of the simulation of the 3D scene.